package com.peng.leetcode.array;

import java.util.*;

/**
 * SubsetsWithDup
 * <p>
 * 90. 子集 II
 *
 * @author: lupeng6
 * @create: 2021/3/31 10:38
 */
public class SubsetsWithDup {

    /**
     * 子集问题， 使用回溯算法， 每个元素分为选择和不选择两种。
     *
     * @author lupeng6
     * @date 2021/3/31 10:56
     */
    public static void main(String[] args) {
        int[] nums = {1, 2, 2};
        System.out.println(new SubsetsWithDup().subsetsWithDup(nums));
    }


    private Set<List<Integer>> answer = new HashSet<>();

    private int[] nums;

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new ArrayList<>();
        }
        Arrays.sort(nums);
        this.nums = nums;
        dfs(0, new ArrayList<>());
        return new ArrayList<>(answer);
    }


    private void dfs(int index, List<Integer> list) {
        if (index == nums.length) {
            answer.add(new ArrayList<>(list));
            return;
        }
        list.add(nums[index]);
        dfs(index + 1, list);


        list.remove(list.size() - 1);
        dfs(index + 1, list);
    }

}
